#include "dynamic_programming.h"

#include "log.h"
#include "perf_timer.h"

namespace {
constexpr uint32_t STAIR_FLOORS = 40;
}

void IDynamicProgramming::Executor()
{
    Base::Utils::PerfTimerMs timerMs;
    auto result = ClimbStairs(STAIR_FLOORS);
    auto elapsed = timerMs.Elapsed();
    SYS_LOG(_INFO) << descriptor_ << ": 爬" << STAIR_FLOORS << "级楼梯有 " << result << " 种方法, 耗时: " <<
        elapsed << " ms" << '\n';
}

int32_t ViolentRecursion::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    return ClimbStairs(stairFloors - 1) + ClimbStairs(stairFloors - 2);
}

int32_t MemoryBasedSearch::Dfs(uint32_t stairFloors, std::vector<int32_t> &memo)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    if (memo[stairFloors] != -1) {
        return memo[stairFloors];
    }
    memo[stairFloors] = Dfs(stairFloors - 1, memo) + Dfs(stairFloors - 2, memo);
    return memo[stairFloors];
}

int32_t MemoryBasedSearch::ClimbStairs(uint32_t stairFloors)
{
    std::vector<int32_t> memo(stairFloors + 1, -1);
    return Dfs(stairFloors, memo);
}

int32_t DynamicProgramming::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    std::vector<int32_t> dp(stairFloors + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (uint32_t i = 3; i <= stairFloors; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[stairFloors];
}

int32_t PerfDynamicProgramming::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    int32_t prev2 = 1; // dp[i-2]
    int32_t prev1 = 2; // dp[i-1]
    int32_t current;

    for (uint32_t i = 3; i <= stairFloors; ++i) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}